"""
实现二叉树与二叉树的后序遍历非递归实现
"""

class BinaryNode:
    """
    定义二叉树结点
    """
    def __init__(self,value=None,left=None,right=None):
        self.value = value
        self.left = left
        self.right = right
        self.result = None #每个节点附加的数据
        self.enum_list = None
        self.enum_i = 0
        self.enum_length = 0
    
    def __next__(self):
        """
        实现迭代器__next__方法
        """
        if self.enum_i < self.enum_length:
            self.enum_i += 1
            return self.enum_list[self.enum_i-1]
        else:
            self.enum_length = 0
            self.enum_list = None
            raise StopIteration

    def __iter__(self):
        """
        实现迭代器__iter__方法
        后序遍历非递归实现
        """
        self.enum_list = []
        stack = []
        tree_node = self
        last_visit = None
        while tree_node or stack:
            while tree_node and isinstance(tree_node,BinaryNode):
                stack.append(tree_node)
                tree_node = tree_node.left
            if stack:
                tree_node = stack.pop()
                if not isinstance(tree_node.right,BinaryNode) or tree_node.right == last_visit:
                    self.enum_list.append(tree_node)
                    last_visit = tree_node
                    tree_node = None
                else:
                    stack.append(tree_node)
                    tree_node = tree_node.right
        self.enum_i = 0
        self.enum_length = len(self.enum_list)
        return self
